相关链接
题目传送门:https://www.codechef.com/problems/PRIMEDST
官方题解:https://www.codechef.com/problems/PRIMEDST
神犇题解:https://stalker-blog.apphb.com/post/divide-and-conquer-on-trees-based-on-vertexes
解题报告
考虑使用点分治来统计答案,实际是求
\(\sum\limits_{i + j = prime\_number} {nu{m_i} \cdot nu{m_j}}\)
然后发现这货是个卷积的形式,于是点分的时候搞一搞FFT就可以啦!
值得注意的是,在FFT的时候答案可能会爆int
不要问我是怎么知道的
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 66000; const int M = 110000; const int INF = 1e9; const double EPS = 1e-2; const double PI = acos(-1); int n,head[N],to[M],nxt[M]; LL vout; inline void Add_Edge(int u, int v) { static int T = 0; to[++T] = v; nxt[T] = head[u]; head[u] = T; to[++T] = u; nxt[T] = head[v]; head[v] = T; } inline int read() { char c=getchar(); int f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } class Fast_Fourier_Transform{ typedef complex<double> E; complex<double> a[N<<1]; int pri[M],vis[M],pos[N<<1],tot,len,stp; public: Fast_Fourier_Transform() { for (int i=2;i<M;i++) { if (!vis[i]) pri[++tot] = i; for (int j=1;j<=tot&&pri[j]*i<M;j++) { vis[i*pri[j]] = 1; if (i%pri[j] == 0) break; } } } inline LL solve(int t, int *arr) { for (len=1,stp=-1;len<=t*2;len<<=1,++stp); memset(a,0,sizeof(E)*(len+9)); for (int i=0;i<=t;i++) a[i].real() = arr[i]; for (int i=1;i<len;i++) { pos[i] = pos[i>>1] >> 1; if (i & 1) pos[i] |= 1 << stp; } fft(a, 1); for (int i=0;i<len;i++) a[i] *= a[i]; fft(a, -1); LL ret = 0; for (int i=1;i<=tot&&pri[i]<=t*2;i++) ret += a[pri[i]].real() / len + EPS; return ret; } private: inline void fft(E *arr, int t) { for (int i=0;i<len;i++) if (pos[i] < i) swap(arr[pos[i]], arr[i]); for (int k=0,gap=2;k<=stp;k++,gap<<=1) { E wn(cos(2*PI/gap),t*sin(2*PI/gap)); for (int j=0;j<len;j+=gap) { complex<double> cur(1, 0),t1,t2; for (int i=j;i<j+gap/2;i++,cur*=wn) { t1 = arr[i]; t2 = cur * arr[i+gap/2]; arr[i] = t1 + t2; arr[i+gap/2] = t1 - t2; } } } } }FFT; class Node_Based_Divide_and_Conquer{ int area_size,cur_ans,root,tot; int sum[N],vis[N],cnt[N]; public: inline void solve() { area_size = n; cur_ans = INF; Get_Root(1, 1); work(root, area_size); } private: void work(int w, int sz) { vis[w] = 1; vout += solve(w, 0); for (int i=head[w];i;i=nxt[i]) { if (!vis[to[i]]) { vout -= solve(to[i], 1); area_size = sum[to[i]]<sum[w]? sum[to[i]]: sz - sum[w]; cur_ans = INF; Get_Root(to[i], w); work(root, area_size); } } } void Get_Root(int w, int f) { int mx = 0; sum[w] = 1; for (int i=head[w];i;i=nxt[i]) { if (to[i] != f && !vis[to[i]]) { Get_Root(to[i], w); sum[w] += sum[to[i]]; mx = max(mx, sum[to[i]]); } } mx = max(mx, area_size - sum[w]); if (mx < cur_ans) { cur_ans = mx; root = w; } } LL solve(int w, int bas) { memset(cnt,0,sizeof(int)*(tot+9)); tot = 0; Get_Dis(w, bas, w); return FFT.solve(tot, cnt); } void Get_Dis(int w, int d, int f) { cnt[d]++; tot = max(tot, d); for (int i=head[w];i;i=nxt[i]) if (to[i] != f && !vis[to[i]]) Get_Dis(to[i], d+1, w); } }NDC; int main() { n = read(); for (int i=1;i<n;i++) Add_Edge(read(), read()); NDC.solve(); printf("%.10lf\n",(double)vout/n/(n-1)); return 0; }
It’s genuinely very difficult in this full of activity life to listen news on Television, so I
only use web for that purpose, and obtain the latest information.
I quite like reading through a post that will make people think.
Also, many thanks for allowing for me to comment!
Thank you a bunch for sharing this with all of
us you really understand what you’re talking approximately!
Bookmarked. Please additionally visit my site =). We will have a hyperlink alternate
agreement among us
After exploring a number of the blog posts on your
website, I honestly like your way of blogging. I added it
to my bookmark site list and will be checking back in the
near future. Take a look at my website as well and tell me
what you think.
I’m gone to inform my little brother, that he should also pay a visit this webpage on regular basis to get updated from
most recent reports.
I have been surfing online more than three hours today, yet I never found any interesting article like
yours. It’s pretty worth enough for me. In my view, if all site owners
and bloggers made good content as you did, the internet will be much more useful than ever before.
Howdy! This is my first visit to your blog! We are a team of volunteers and starting a new project in a community in the same niche.
Your blog provided us valuable information to work on. You have done a extraordinary job!
Valuable information. Lucky me I found your site by accident, and I am shocked why this accident did not happened earlier! I bookmarked it.
Thanks for finally writing about >【CodeChef PRIMEDST】Prime Distance
On Tree – Qizy’s Database <Liked it!
Greetings! Very helpful advice within this post! It’s the little
changes that make the most important changes. Thanks for sharing!
Thank you for sharing your info. I really appreciate your efforts and I will be waiting for your next post thanks once again.
Excellent blog you have here.. It’s hard to find high-quality writing like
yours these days. I truly appreciate people like you! Take care!!
Hey very nice blog!
Hey I know this is off topic but I was wondering if you knew of any widgets I could add to my
blog that automatically tweet my newest twitter updates.
I’ve been looking for a plug-in like this for quite some time and was hoping maybe you
would have some experience with something like this.
Please let me know if you run into anything. I truly enjoy reading your blog and I look forward to your new updates.
Thank you for the good writeup. It in fact was a amusement account it.
Look advanced to more added agreeable from you!
However, how could we communicate?
I was wondering if you ever considered changing the layout of your website?
Its very well written; I love what youve got to say.
But maybe you could a little more in the way
of content so people could connect with it better. Youve got an awful lot of text for only having one or
two pictures. Maybe you could space it out better?
Link exchange is nothing else however it is only placing the
other person’s webpage link on your page at appropriate place and
other person will also do same in favor of you.
What’s Going down i’m new to this, I stumbled upon this I have found It absolutely
helpful and it has aided me out loads. I am hoping to give a contribution & aid different users like its aided me.
Great job.
When I initially commented I clicked the “Notify me when new comments are added” checkbox and now each time a comment is added I get three e-mails with the same comment.
Is there any way you can remove people from that service?
Thanks a lot!
Heya i’m for the primary time here. I came across this board and
I to find It really useful & it helped me out much.
I am hoping to provide one thing again and aid others such as you helped me.
If you are going for finest contents like myself, just pay a
quick visit this web site all the time as it provides quality contents, thanks
I enjoy the efforts you have put in this, appreciate it for all the great articles.
Really informative blog article.Thanks Again. Want more.